{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #寻找二叉搜索树中的目标节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-search-tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉搜索树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findTargetNode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #寻找二叉搜索树中的目标节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>某公司组织架构以二叉搜索树形式记录，节点值为处于该职位的员工编号。请返回第 <code>cnt</code> 大的员工编号。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode.cn/1695101634-kzHKZW-image.png\" style=\"height: 281px; width: 500px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [7, 3, 9, 1, 5], cnt = 2\n",
    "       7\n",
    "      / \\\n",
    "     3   9\n",
    "    / \\\n",
    "   1   5\n",
    "<strong>输出：</strong>7\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode.cn/1695101636-ESZtLa-image.png\" style=\"height: 281px; width: 500px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> root = [10, 5, 15, 2, 7, null, 20, 1, null, 6, 8], cnt = 4\n",
    "       10\n",
    "      / \\\n",
    "     5   15\n",
    "    / \\    \\\n",
    "   2   7    20\n",
    "  /   / \\ \n",
    " 1   6   8\n",
    "<strong>输出:</strong> 8</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>1 ≤ cnt&nbsp;≤ 二叉搜索树元素个数</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof](https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof](https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[7,3,9,1,5]\\n2', '[10,5,15,2,7,null,20,1,null,6,8]\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inorder(self, root):\n",
    "        if not root:\n",
    "            return []\n",
    "        left = self.inorder(root.left)\n",
    "        right = self.inorder(root.right)\n",
    "        return left + [root.val] + right\n",
    "\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        ls = self.inorder(root)\n",
    "        return ls[-cnt]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        stack = []\n",
    "        res = root.val \n",
    "        while stack or root:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.right\n",
    "            \n",
    "            node = stack.pop()\n",
    "            res = node.val\n",
    "            cnt -= 1\n",
    "            if cnt == 0:\n",
    "                return res \n",
    "            \n",
    "            root = node.left\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        arr = []\n",
    "        def traversal(tree):\n",
    "            if not tree:\n",
    "                return None\n",
    "            traversal(tree.left)\n",
    "            arr.append(tree.val)\n",
    "            traversal(tree.right)\n",
    "        traversal(root)\n",
    "        arr = arr[::-1]\n",
    "        return arr[cnt-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            dfs(root.right)\n",
    "            if self.cnt == 0: return\n",
    "            self.cnt -= 1\n",
    "            if self.cnt == 0: self.res = root.val\n",
    "            dfs(root.left)\n",
    "\n",
    "        self.cnt = cnt\n",
    "        dfs(root)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        ###遍历节点\n",
    "        res = []\n",
    "        def add(root):\n",
    "            if not root: return\n",
    "            res.append(root.val)\n",
    "            add(root.left)\n",
    "            add(root.right)\n",
    "\n",
    "        add(root)\n",
    "        res = sorted(res)\n",
    "        return res[-cnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        ###遍历节点\n",
    "        res = []\n",
    "        def add(root):\n",
    "            res.append(root.val)\n",
    "            if root.left:add(root.left)\n",
    "            if root.right:add(root.right)\n",
    "\n",
    "        add(root)\n",
    "        res = sorted(res)\n",
    "        return res[-cnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        self.i = 0\n",
    "        self.ans = 0\n",
    "        def dfs(node):\n",
    "            if not node:return\n",
    "            dfs(node.right)\n",
    "            self.i+=1\n",
    "            if self.i==cnt: \n",
    "                self.ans = node.val\n",
    "                return\n",
    "            dfs(node.left)\n",
    "        dfs(root)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        def dfs(root):\n",
    "            if not root or self.cnt == 0: return\n",
    "            dfs(root.right)\n",
    "            self.cnt -= 1\n",
    "            if self.cnt == 0: \n",
    "                self.res = root.val\n",
    "                return \n",
    "            dfs(root.left)\n",
    "\n",
    "        self.cnt = cnt\n",
    "        dfs(root)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        def dfs(cur):\n",
    "            if not cur: return\n",
    "            dfs(cur.right)\n",
    "            self.cnt -= 1\n",
    "            if self.cnt == 0:\n",
    "                self.res = cur.val\n",
    "                return \n",
    "            dfs(cur.left)\n",
    "        \n",
    "        self.cnt = cnt\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        self.cnt = cnt\n",
    "        self.ans = 0\n",
    "\n",
    "        def dfs(node):\n",
    "            if node is None: return \n",
    "            dfs(node.right)\n",
    "            if self.cnt == 0: return\n",
    "            self.cnt = self.cnt - 1\n",
    "            if self.cnt == 0 :\n",
    "                self.ans = node.val \n",
    "            dfs(node.left)\n",
    "            return \n",
    "\n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        #   优先遍历右子树，再是根节点，最后是左子树\n",
    "        # self.res=0\n",
    "        def dfs(T):\n",
    "            if not T:\n",
    "                return\n",
    "            dfs(T.right)\n",
    "            if self.cnt==0:\n",
    "                return\n",
    "            self.cnt-=1\n",
    "            if self.cnt==0:\n",
    "                self.res=T.val\n",
    "            dfs(T.left)\n",
    "        self.cnt=cnt\n",
    "        dfs(root)\n",
    "        return self.res\n",
    "\n",
    "        # def dfs(root):\n",
    "        #     if not root: return\n",
    "        #     dfs(root.right)\n",
    "        #     if self.cnt == 0: return\n",
    "        #     self.cnt -= 1\n",
    "        #     if self.cnt == 0: self.res = root.val\n",
    "        #     dfs(root.left)\n",
    "\n",
    "        # self.cnt = cnt\n",
    "        # dfs(root)\n",
    "        # return self.res\n",
    "\n",
    "    #    dfs(root)\n",
    "    #     res=0\n",
    "    #     if not root:\n",
    "    #         return 0\n",
    "    #     self.findTargetNode(root.right,cnt)\n",
    "    #     if cnt==0:\n",
    "    #         return 0\n",
    "    #     cnt-=1  \n",
    "    #     if cnt==0:\n",
    "    #         res=root.val\n",
    "    #     print(cnt)\n",
    "    #     self.findTargetNode(root.left,cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.count = 0\n",
    "        self.res = 0\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        if not root:\n",
    "            return None\n",
    "        self.reversed_mid_travel(root, cnt)\n",
    "        return self.res\n",
    "        \n",
    "    def reversed_mid_travel(self, root, cnt):\n",
    "        if not root:\n",
    "            return None\n",
    "        self.reversed_mid_travel(root.right, cnt)\n",
    "        self.count += 1\n",
    "        if self.count == cnt:\n",
    "            self.res = root.val\n",
    "            return \n",
    "        self.reversed_mid_travel(root.left, cnt)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        def travel(head):\n",
    "            if not head:\n",
    "                return\n",
    "            travel(head.right)\n",
    "            if self.cnt == 0: \n",
    "                return\n",
    "            self.cnt -= 1\n",
    "            if self.cnt == 0: \n",
    "                self.res = head.val\n",
    "            travel(head.left)\n",
    "\n",
    "        self.cnt = cnt\n",
    "        travel(root)\n",
    "        \n",
    "        return self.res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: TreeNode, cnt: int) -> int:\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            dfs(root.right)\n",
    "            if self.cnt == 0: return\n",
    "            self.cnt -= 1\n",
    "            if self.cnt == 0: self.res = root.val\n",
    "            dfs(root.left)\n",
    "\n",
    "        self.cnt = cnt\n",
    "        dfs(root)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: TreeNode, cnt: int) -> int:\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            dfs(root.right)\n",
    "            if self.cnt == 0: return\n",
    "            self.cnt -= 1\n",
    "            if self.cnt == 0: self.res = root.val\n",
    "            dfs(root.left)\n",
    "\n",
    "        self.cnt = cnt\n",
    "        dfs(root)\n",
    "        return self.res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        #   优先遍历右子树，再是根节点，最后是左子树\n",
    "        # self.res=0\n",
    "        # def dfs(T):\n",
    "        #     if not T:\n",
    "        #         return 0\n",
    "        #     dfs(T.right)\n",
    "        #     if self.cnt==0:\n",
    "        #         return 0\n",
    "        #     self.cnt-=1\n",
    "        #     if self.cnt==0:\n",
    "        #         self.res=root.val\n",
    "        #     dfs(T.left)\n",
    "        # self.cnt=cnt\n",
    "        # dfs(root)\n",
    "        # return self.res\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            dfs(root.right)\n",
    "            if self.cnt == 0: return\n",
    "            self.cnt -= 1\n",
    "            if self.cnt == 0: self.res = root.val\n",
    "            dfs(root.left)\n",
    "\n",
    "        self.cnt = cnt\n",
    "        dfs(root)\n",
    "        return self.res\n",
    "\n",
    "    #    dfs(root)\n",
    "    #     res=0\n",
    "    #     if not root:\n",
    "    #         return 0\n",
    "    #     self.findTargetNode(root.right,cnt)\n",
    "    #     if cnt==0:\n",
    "    #         return 0\n",
    "    #     cnt-=1  \n",
    "    #     if cnt==0:\n",
    "    #         res=root.val\n",
    "    #     print(cnt)\n",
    "    #     self.findTargetNode(root.left,cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: TreeNode, k: int) -> int:\n",
    "        # def dfs(root):\n",
    "        #     if not root: \n",
    "        #         return\n",
    "        #     dfs(root.right)\n",
    "        #     if self.k == 0: \n",
    "        #         return\n",
    "        #     self.k -= 1\n",
    "        #     if self.k == 0: \n",
    "        #         self.res = root.val\n",
    "        #     dfs(root.left)\n",
    "        # self.k = k\n",
    "        # dfs(root)\n",
    "        # return self.res\n",
    "        def dfs(root):\n",
    "            if not root: \n",
    "                return \n",
    "            dfs(root.left)\n",
    "            res.append(root.val)\n",
    "            dfs(root.right)\n",
    "        res = list()\n",
    "        dfs(root)\n",
    "        return res[-k]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def traverse(self, root, cnt):\n",
    "        if root is None:\n",
    "            return\n",
    "        self.traverse(root.right, cnt)\n",
    "        self.k += 1\n",
    "        if self.k == cnt:\n",
    "            self.res = root.val\n",
    "            return\n",
    "        self.traverse(root.left, cnt)\n",
    "                \n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        self.k = 0\n",
    "        self.res = 0\n",
    "        self.traverse(root, cnt)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        \n",
    "        global nums\n",
    "        nums = []\n",
    "        self.midfun(root)\n",
    "        return nums[-cnt]\n",
    "        \n",
    "\n",
    "    def midfun(self,root):\n",
    "\n",
    "        if root == None:\n",
    "            return\n",
    "        \n",
    "        self.midfun(root.left)\n",
    "        nums.append(root.val)\n",
    "        self.midfun(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        res = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "\n",
    "            dfs(root.right)\n",
    "            res.append(root.val)\n",
    "            dfs(root.left)\n",
    "        dfs(root)\n",
    "        print (res)\n",
    "        return res[cnt-1] \n",
    " \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: TreeNode, cnt: int) -> int:\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            dfs(root.right)\n",
    "            self.cnt -= 1\n",
    "            if self.cnt == 0: self.res = root.val\n",
    "            dfs(root.left)\n",
    "\n",
    "        self.cnt = cnt\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self,root,res):\n",
    "        if not root:\n",
    "            return 0\n",
    "        self.dfs(root.right,res)\n",
    "        res.append(root.val)\n",
    "        self.dfs(root.left,res)\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        res=[]\n",
    "        self.dfs(root,res)\n",
    "        return res[cnt-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        # 中序遍历：二叉搜索树就是从小到大排列！\n",
    "        k, res = cnt, 0\n",
    "        def inorder(root): # 逆 中序（从大到小）\n",
    "            nonlocal k, res\n",
    "            if not root: return \n",
    "\n",
    "            inorder(root.right)\n",
    "            # if k == 0: return \n",
    "            k -= 1\n",
    "            if k == 0: \n",
    "                res = root.val\n",
    "                return \n",
    "            inorder(root.left)\n",
    "        inorder(root)\n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.right)\n",
    "            if self.cnt == 0:\n",
    "                return\n",
    "            if self.cnt == 1:\n",
    "                self.res = root.val\n",
    "            self.cnt -= 1\n",
    "            dfs(root.left)\n",
    "        self.cnt = cnt\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        self.k = cnt\n",
    "        def recur(node):\n",
    "            if not node:\n",
    "                return\n",
    "            recur(node.right)\n",
    "            if not self.k:\n",
    "                return\n",
    "            self.k -= 1\n",
    "            if not self.k:\n",
    "                self.res = node.val\n",
    "                return\n",
    "            recur(node.left)\n",
    "        self.res = 0\n",
    "        recur(root)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        # 中序：左根右，从小到大\n",
    "        # 逆序：右根左遍历，从大到小\n",
    "        \n",
    "        \n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            \n",
    "            dfs(root.right)\n",
    "            self.i += 1\n",
    "            if self.i == cnt:\n",
    "                self.res = root.val\n",
    "            dfs(root.left)\n",
    "\n",
    "        if not root:\n",
    "            return\n",
    "        self.i = 0\n",
    "        dfs(root)\n",
    "        \n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        \n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.right)\n",
    "            if self.cnt == 0:\n",
    "                return\n",
    "            self.cnt -= 1\n",
    "            if self.cnt == 0:\n",
    "                self.res = root.val\n",
    "            dfs(root.left)\n",
    "\n",
    "        self.cnt = cnt\n",
    "        dfs(root)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        idx = 0\n",
    "        ans = None\n",
    "        def dfs(root):\n",
    "            nonlocal ans, idx\n",
    "            if root is None: return\n",
    "            dfs(root.right)\n",
    "            idx += 1\n",
    "            if idx == cnt:\n",
    "                ans = root.val\n",
    "                return\n",
    "            dfs(root.left)\n",
    "        dfs(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            dfs(root.right)\n",
    "            if self.cnt == 0: return\n",
    "            self.cnt -= 1\n",
    "            if self.cnt == 0: self.res = root.val\n",
    "            dfs(root.left)\n",
    "\n",
    "        self.cnt = cnt\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        def countTree(root):\n",
    "            if not root: return 0\n",
    "            return countTree(root.left) + countTree(root.right) + 1\n",
    "        \n",
    "        rcnt = 0 if not root else countTree(root.right)\n",
    "        if cnt == rcnt+1:\n",
    "            return root.val\n",
    "        elif cnt <= rcnt:\n",
    "            return self.findTargetNode(root.right, cnt)\n",
    "        else:\n",
    "            return self.findTargetNode(root.left, cnt-rcnt-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        stk = []\n",
    "        cur = root\n",
    "        k = cnt\n",
    "        while cur or stk:\n",
    "            while cur:\n",
    "                stk.append(cur)\n",
    "                cur = cur.right\n",
    "            cur = stk.pop()\n",
    "            if k <= 1:\n",
    "                return cur.val\n",
    "            cur = cur.left\n",
    "            k -= 1\n",
    "        return None\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        def dfs(root):\n",
    "            if not root: return \n",
    "            dfs(root.right)\n",
    "            if self.cnt == 0:return\n",
    "            self.cnt -=1\n",
    "            if self.cnt == 0:self.res = root.val\n",
    "            dfs(root.left)\n",
    "\n",
    "        self.cnt = cnt\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        self.res = []\n",
    "\n",
    "        def order(node):\n",
    "            if node is None:\n",
    "                return\n",
    "            \n",
    "            order(node.left)\n",
    "            self.res.append(node.val)\n",
    "            order(node.right)\n",
    "        \n",
    "        order(root)\n",
    "\n",
    "        return self.res[len(self.res)-cnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetNode(self, root, cnt):\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.right)\n",
    "            if self.cnt == 0:\n",
    "                return\n",
    "            self.cnt -= 1\n",
    "            if self.cnt == 0:\n",
    "                self.res = root.val\n",
    "            dfs(root.left)\n",
    "\n",
    "        self.cnt = cnt\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        if not root: return\n",
    "        self.pre = None\n",
    "        def dfs(cur):\n",
    "            if not cur: return\n",
    "            dfs(cur.right)\n",
    "            if self.pre: self.pre.left, cur.right = cur, self.pre\n",
    "            else: self.head = cur\n",
    "            self.pre = cur\n",
    "            dfs(cur.left)\n",
    "        dfs(root)\n",
    "        res = TreeNode()\n",
    "        res.left = self.head\n",
    "        for i in range(cnt):\n",
    "            res = res.left\n",
    "        return res.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetNode(self, root, cnt):\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.right)\n",
    "            if self.cnt == 0:\n",
    "                return\n",
    "            self.cnt -= 1\n",
    "            if self.cnt == 0:\n",
    "                self.res = root.val\n",
    "                return\n",
    "            dfs(root.left)\n",
    "\n",
    "        self.cnt = cnt\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        if not root: return\n",
    "        self.pre = None\n",
    "        def dfs(cur):\n",
    "            if not cur: return\n",
    "            dfs(cur.right)\n",
    "            if self.pre: self.pre.left, cur.right = cur, self.pre\n",
    "            else: self.head = cur\n",
    "            self.pre = cur\n",
    "            dfs(cur.left)\n",
    "        dfs(root)\n",
    "        res = TreeNode()\n",
    "        res.left = self.head\n",
    "        for i in range(cnt):\n",
    "            res = res.left\n",
    "        return res.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        self.ct = 0\n",
    "        def dfs(node):\n",
    "            if not node:return\n",
    "            # if node.right:\n",
    "            dfs(node.right)\n",
    "            \n",
    "            self.ct += 1\n",
    "            if self.ct == cnt:\n",
    "                self.res = node.val\n",
    "\n",
    "            # if node.left:\n",
    "            dfs(node.left)\n",
    "            \n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        def dfs(root):\n",
    "            if not root : return \n",
    "            dfs(root.right)\n",
    "            if self.cnt == 0 : return \n",
    "            self.cnt -= 1\n",
    "            if self.cnt == 0 : self.res = root.val\n",
    "            dfs(root.left)\n",
    "            \n",
    "        self.cnt = cnt\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        # 中序：左根右，从小到大\n",
    "        # 逆序：右根左遍历，从大到小\n",
    "        \n",
    "        \n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            \n",
    "            dfs(root.right)\n",
    "            self.i += 1\n",
    "            if self.i == cnt:\n",
    "                self.res = root.val\n",
    "                return root.val\n",
    "            dfs(root.left)\n",
    "\n",
    "        if not root:\n",
    "            return -1\n",
    "        self.i = 0\n",
    "        self.res = 0\n",
    "        dfs(root)\n",
    "        \n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        if not root: return None\n",
    "\n",
    "        def dfs(cur):\n",
    "            if not cur: return\n",
    "            dfs(cur.right)\n",
    "            \n",
    "            if self.cnt == 0: return\n",
    "            self.cnt -= 1\n",
    "            if self.cnt == 0:\n",
    "                self.res = cur.val\n",
    "\n",
    "            dfs(cur.left)\n",
    "\n",
    "        self.cnt = cnt\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        def recur(node):\n",
    "            if node is None:\n",
    "                return \n",
    "            recur(node.left)\n",
    "            queue.append(node.val)\n",
    "            recur(node.right)\n",
    "        \n",
    "        if not root: return\n",
    "        queue=[]\n",
    "        recur(root)\n",
    "        return queue[-cnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        if not root:\n",
    "            return None\n",
    "        stack=[]\n",
    "        res=[]\n",
    "        p=root\n",
    "        while p or stack:\n",
    "            if p:\n",
    "                stack.append(p)\n",
    "                p=p.left\n",
    "            else:\n",
    "                p=stack.pop()\n",
    "                res.append(p.val)\n",
    "                p=p.right\n",
    "        return res[-cnt]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        self.ct = 0\n",
    "        def dfs(node):\n",
    "            if not node:return\n",
    "            if node.right:\n",
    "                dfs(node.right)\n",
    "            \n",
    "            self.ct += 1\n",
    "            if self.ct == cnt:\n",
    "                self.res = node.val\n",
    "\n",
    "            if node.left:\n",
    "                dfs(node.left)\n",
    "            \n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        def dfs(cur):\n",
    "            if not cur: return\n",
    "            dfs(cur.right)\n",
    "            self.cnt -= 1\n",
    "            if self.cnt == 0: \n",
    "                self.res = cur.val\n",
    "                return\n",
    "            dfs(cur.left)\n",
    "\n",
    "        self.cnt = cnt\n",
    "        dfs(root)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        # 中序遍历\n",
    "        t=0\n",
    "        result=0\n",
    "\n",
    "        def dfs(cur):\n",
    "            nonlocal t,result,cnt\n",
    "            if not cur or t>=cnt:\n",
    "                return\n",
    "            dfs(cur.right)\n",
    "            t+=1\n",
    "            if t==cnt:\n",
    "                result=cur.val\n",
    "                return\n",
    "            dfs(cur.left)\n",
    "        dfs(root)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        self.ct = 0\n",
    "        def dfs(node):\n",
    "            if not node:return\n",
    "            if node.right:\n",
    "                dfs(node.right)\n",
    "            if self.ct == cnt:\n",
    "                return\n",
    "            self.ct += 1\n",
    "            if self.ct == cnt:\n",
    "                self.res = node.val\n",
    "\n",
    "            if node.left:\n",
    "                dfs(node.left)\n",
    "            \n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        def dfs(root):\n",
    "            if not root : return \n",
    "            dfs(root.right)\n",
    "            if self.cnt == 0 : return \n",
    "            self.cnt -= 1\n",
    "            if self.cnt == 0 : self.res = root.val\n",
    "            dfs(root.left)\n",
    "            \n",
    "        self.cnt = cnt\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: TreeNode, cnt: int) -> int:\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            dfs(root.right)\n",
    "            self.cnt -= 1\n",
    "            if self.cnt == 0: self.res = root.val\n",
    "            dfs(root.left)\n",
    "\n",
    "        self.cnt = cnt\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        if not root: return\n",
    "        self.pre = None\n",
    "        def dfs(cur):\n",
    "            if not cur: return\n",
    "            dfs(cur.right)\n",
    "            if self.pre: self.pre.left, cur.right = cur, self.pre\n",
    "            else: self.head = cur\n",
    "            self.pre = cur\n",
    "            dfs(cur.left)\n",
    "        dfs(root)\n",
    "        res = TreeNode()\n",
    "        res.left = self.head\n",
    "        for i in range(cnt):\n",
    "            res = res.left\n",
    "        return res.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        remain = cnt\n",
    "        res = None\n",
    "        def dfs(root):\n",
    "            nonlocal remain, res\n",
    "            if not root: return\n",
    "            dfs(root.right)\n",
    "            if remain <=0 : return\n",
    "            if remain == 1: res = root.val\n",
    "            remain -= 1\n",
    "            dfs(root.left)\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        # 中序：左根右，从小到大\n",
    "        # 逆序：右根左遍历，从大到小\n",
    "         \n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.right)\n",
    "            self.i += 1\n",
    "            if self.i == cnt:\n",
    "                self.res = root.val\n",
    "                return\n",
    "            dfs(root.left)\n",
    "\n",
    "        if not root:\n",
    "            return\n",
    "        self.i = 0\n",
    "        dfs(root)\n",
    "        \n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        def dfs(node: TreeNode):\n",
    "            if node.right:\n",
    "                yield from dfs(node.right)\n",
    "            yield node.val\n",
    "            if node.left:\n",
    "                yield from dfs(node.left)\n",
    "        \n",
    "        xs = dfs(root)\n",
    "        value = 0\n",
    "        for i in range(cnt):\n",
    "            value = next(xs)\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        \n",
    "        res = []\n",
    "        def rec(root):\n",
    "            if root==None:\n",
    "                return \n",
    "            rec(root.left)\n",
    "            res.append(root.val)\n",
    "            rec(root.right)\n",
    "\n",
    "        rec(root)    \n",
    "\n",
    "        return res[-cnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        def inorder(cur):\n",
    "            if not cur:return\n",
    "            inorder(cur.left)\n",
    "            tmp.append(cur.val)\n",
    "            inorder(cur.right)\n",
    "\n",
    "        if not root:return\n",
    "        tmp = []\n",
    "        inorder(root)\n",
    "#        tmp.reverse()\n",
    "        return tmp[-cnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        res = []\n",
    "        def fun(root):\n",
    "            if not root:\n",
    "                return \n",
    "            res.append(root.val)\n",
    "            fun(root.left)\n",
    "            fun(root.right)\n",
    "        fun(root)\n",
    "        res.sort()\n",
    "        return res[-cnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:\n",
    "        res = []\n",
    "        def getRes(root):\n",
    "            nonlocal res\n",
    "            if root == None:\n",
    "                return\n",
    "            getRes(root.left)\n",
    "            res.append(root.val)\n",
    "            getRes(root.right)\n",
    "        \n",
    "        getRes(root)\n",
    "        \n",
    "        return res[-cnt]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
